#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <iomanip>

using namespace std;

// 产生式结构体
struct Production {
    string left;    // 产生式左部
    vector<string> right;   // 产生式右部
};

typedef set<string>::const_iterator SetStringIterator;
typedef vector<string>::const_iterator VectorStringIterator;
typedef map<string, set<string> >::const_iterator MapStringIterator;
typedef vector<Production>::const_iterator VectorProductionIterator;

map<string, vector<int> > grammar_dict;
vector<Production> grammar;                 // 产生式集合
set<string> symbols;                        // 文法所有符号集
set<string> nonterminal_symbols;            // 非终结符集合
set<string> terminal_symbols;               // 终结符集合
map<string, set<string> > FIRST;            // FIRST集合
map<string, set<string> > FOLLOW;           // FOLLOW集合
vector<set<pair<int, int> > > COLLECTION;   // 项目集规范簇
vector<map<string, int> > GOTO;             // slr分析表
string  Begin;      // 文法产生符号

// 读取文法
void read_grammar() {
    ifstream file("grammar.txt");
    string line;
    bool flag=true;

    // 逐行读取文法产生式
    while (getline(file, line)) {
        // 处理每行产生式
        stringstream ss(line);
        string index, dot, left, arrow, right_part, se;
        //getline(ss, index, '.');  // Read the rule number
        //getline(ss, dot, '\t');   // Skip the dot and tab
        getline(ss, left, ' ');   // Read the left-hand side of the production
        getline(ss, arrow, ' ');  // Skip the arrow part
        getline(ss, right_part);  // Read the right-hand side of the production
        //getline(ss,se);
        // cout<<left<<'\t'<<arrow<<'\t'<<right_part<<'\n';
        Production prod;

        // 处理产生式左部
        prod.left = left;
        if(flag)
        {
            // 文法产生符号
            Begin=left;
            // cout << Begin << endl;
            flag=false;
        }
        nonterminal_symbols.insert(left);   // 产生式左部都是非终结符

        // 处理产生式右部
        stringstream rs(right_part);
        string symbol;
        while (rs >> symbol) {
            prod.right.push_back(symbol);
            symbols.insert(symbol); // 加入 所有符号集
        }

        // 将当前产生式加入到产生式集合中
        grammar.push_back(prod);    // 下标从 0 开始
        // 为每个产生式标序号
        grammar_dict[left].push_back(grammar.size()-1);
    }
    symbols.insert("#");    // 加入 句末符

    // 打印读取到的 产生式
    // for(int it=0;it<grammar.size();it++)
    // {   
    //     cout<<it<<'\t'<<grammar[it].left<<" -> ";// 左部
    //     for(int it1=0;it1<grammar[it].right.size();it1++)
    //         cout<<grammar[it].right[it1]<<" ";// 右部
    //     cout<<endl;
    // }

    // 打印所有非终结符
    // for(SetStringIterator it = nonterminal_symbols.begin();it!=nonterminal_symbols.end();it++)
    //     cout<<*it<<" ";
    // cout<<endl;
}

// 计算first集合
void compute_first() {
    bool changed = true;
    while (changed) {
        changed = false;
        // 遍历所有产生式
        for (VectorProductionIterator prod=grammar.begin();prod<grammar.end();prod++) {
            // 获取当前非终结符的 FIRST集 及其 长度
            set<string> first = FIRST[prod->left];
            size_t original_size = first.size();

            // 计算 first集
            if (prod->right.empty()) {  // 考虑 空串 的情况
                first.insert("$");
            } else {
                bool all_nullable = true;
                // 遍历当前产生式 右部 所有符号
                for (VectorStringIterator symbol=prod->right.begin();symbol<prod->right.end();symbol++) {
                    // 如果当前符号是非终结符
                    if (nonterminal_symbols.count(*symbol)) {
                        set<string> temp(FIRST[*symbol].begin(), FIRST[*symbol].end());
                        temp.erase("$");
                        first.insert(temp.begin(), temp.end());
                        if (FIRST[*symbol].count("$") == 0) {
                            all_nullable = false;
                            break;
                        }
                    }
                    // 当前符号是终结符
                    else {
                        first.insert(*symbol);  // 将该终结符加入 FIRST集
                        all_nullable = false;
                        break;
                    }
                }
                if (all_nullable) {
                    first.insert("$");
                }
            }

            // 非终结符的FIRST集有更新
            if (first.size() != original_size) {
                changed = true;
            }
            // 更新FIRST集
            FIRST[prod->left]=first;
        }
    }

    // 打印 FIRST集
    // for(map<string, set<string> >::iterator it=FIRST.begin();it!=FIRST.end();it++)
    // {
    // 	cout<<"FIRST("<<it->first<<"):"<<" ";
    // 	for(set<string>::iterator it1=it->second.begin();it1!=it->second.end();it1++)
	// 		cout<<*it1<<" ";
	// 	cout<<endl; 
	// }
}

// 计算follow集合
void compute_follow() {
    FOLLOW[Begin].insert("#");  // Start symbol

    bool changed = true;
    while (changed) {
        changed = false;
        // 遍历所有产生式
        for (VectorProductionIterator prod=grammar.begin();prod<grammar.end();prod++) {
            // 获取当前产生式的 follow集
            set<string> followA = FOLLOW[prod->left];
            // 遍历产生式 右部
            for (size_t i = 0; i < prod->right.size(); ++i) {
                const string& B = prod->right[i];

                // 若当前右部符号是 非终结符
                if (nonterminal_symbols.count(B)) {
                    set<string> followB = FOLLOW[B];
                    size_t original_size = followB.size();
                    bool all_nullable = true;
                    for (size_t j = i + 1; j < prod->right.size(); ++j) {
                        const string& beta = prod->right[j];
                        if (nonterminal_symbols.count(beta)) {
                            set<string> firstBeta(FIRST[beta].begin(), FIRST[beta].end());
                            firstBeta.erase("$");
                            followB.insert(firstBeta.begin(), firstBeta.end());
                            if (FIRST[beta].count("$") == 0) {
                                all_nullable = false;
                                break;
                            }
                        } else {
                            followB.insert(beta);
                            all_nullable = false;
                            break;
                        }
                    }
                    if (all_nullable || i==prod->right.size()-1) {
                        followB.insert(followA.begin(), followA.end());
                    }
                    if (followB.size() != original_size) {
                        changed = true;
                    }
                    FOLLOW[B]=followB;
                }
            }
        }
    }

    // 打印 follow集
    // for(map<string, set<string> >::iterator it=FOLLOW.begin();it!=FOLLOW.end();it++)
    // {
    // 	cout<<"FOLLOW("<<it->first<<"):"<<" ";
    // 	for(set<string>::iterator it1=it->second.begin();it1!=it->second.end();it1++)
	// 		cout<<*it1<<" ";
	// 	cout<<endl; 
	// }
}

// 计算给定项目集的 闭包
void closure(set<pair<int, int> >& items) {
    /* 
        参数含义：
        items： 给定项目集 
    */
    // cout << "compute closure:\n";

    bool changed = true;
    while (changed) {
        changed = false;
        set<pair<int, int> > new_items; // 新增 等价项目集
        // 遍历给定项目集
        for (set<pair<int, int> >::const_iterator item=items.begin();item!=items.end();item++) {
            // cout << item->first << ' ' << item->second << endl;
            // cout << grammar[item->first].left << " -> " << grammar[item->first].right[item->second] << endl;
            
            // 当前项目未达到 归约状态
            if (item->second < grammar[item->first].right.size()) {
                // 寻找非终结符
                string B = grammar[item->first].right[item->second];
                if (nonterminal_symbols.find(B) != nonterminal_symbols.end()) {
                    // B 是非终结符
                    for (vector<int>::const_iterator i=grammar_dict[B].begin();i<grammar_dict[B].end();i++) {
                        // cout << " i: " << *i <<endl;
                        pair<int, int> new_item = make_pair(*i, 0);     // 新增 等价项目
                        if (items.find(new_item) == items.end() && new_items.find(new_item) == new_items.end()) {
                            new_items.insert(new_item);     // 加入 新增等价项目集
                            changed = true;
                        }
                    }
                }
            }
        }
        // 更新给定项目集
        items.insert(new_items.begin(), new_items.end());
    }

    // 打印给定项目集
    // for (set<pair<int, int> >::const_iterator item=items.begin();item!=items.end();item++){
    //     cout << item->first << " " << item->second << endl;
    // }
}

void compute_goto(set<pair<int, int> >& items, const string& symbol, set<pair<int, int> >& result) {
    /*
        参数含义：
        items：当前项目集
        symbol：输入符号
        result：输出项目集
    */

    // 遍历给定项目集
    for (set<pair<int, int> >::const_iterator item=items.begin();item!=items.end();item++) {
        // 未达归约状态 && 待输入符号==输入符号
        if (item->second < grammar[item->first].right.size() && grammar[item->first].right[item->second] == symbol) {
            result.insert(make_pair(item->first, item->second + 1));
        }
    }
    // 输出项目集 求闭包
    closure(result);
}

// 计算slr表中的 归约动作
void compute_action(set<pair<int, int> >& items){
    /*
        检查给定项目集中是否含有归约项目，若有，则更新slr表（GOTO）

        参数：
        items：给定项目集
    */

    // 遍历给定项目集
    for (set<pair<int, int> >::const_iterator item=items.begin();item!=items.end();item++){
        // 寻找 归约项目
        if (item->second == grammar[item->first].right.size() || (grammar[item->first].right[0]=="$" && item->second==0)){
            // 遍历 当前产生式非终结符 的FOLLOW集 并 更新slr表
            for (set<string>::iterator it=FOLLOW[grammar[item->first].left].begin();it!=FOLLOW[grammar[item->first].left].end();it++){
                // 更新slr表：增加归约动作
                GOTO[COLLECTION.size()][*it] = -item->first - 1;
            }
        }
    }
}

// 构造 slr 分析表
void construct_slr_table() {
    // cout << "construct slr table:\n";

    set<pair<int, int> > start_items;
    start_items.insert(make_pair(0,0)); // 起始项目集
    closure(start_items);   // 计算起始项目集闭包
    COLLECTION.push_back(start_items);  // 将起始项目集加入到 项目集规范簇

    // 遍历 项目集规范簇
    for (size_t i = 0; i < COLLECTION.size(); ++i) {
        // 遍历所有符号表
        for (SetStringIterator symbol=symbols.begin();symbol!=symbols.end();symbol++) {
            // 跳过空串
            if (*symbol=="$") continue;

            // 计算新的项目集
            set<pair<int, int> > goto_items;
            // cout << *symbol<<endl;
            compute_goto(COLLECTION[i], *symbol, goto_items);
            // 若新的项目集 不为空
            if (!goto_items.empty()) {
                vector<set<pair<int, int> > >::iterator it = find(COLLECTION.begin(), COLLECTION.end(), goto_items);
                // 检查目标项目集是否已经存在于 项目及规范簇 中
                if (it == COLLECTION.end()) {   // 不存在
                    GOTO.resize(COLLECTION.size()+1);

                    // 检查新项目集是否可以 归约 并更新GOTO表
                    compute_action(goto_items);

                    COLLECTION.push_back(goto_items);
                    GOTO[i][*symbol] = COLLECTION.size() - 1;   // 更新slr分析表
                } else {    // 存在
                    GOTO[i][*symbol] = distance(COLLECTION.begin(), it);
                }
            }
        }
    }

    // 打印项目集规范簇 COLLECTION
    // for (int i=0;i<COLLECTION.size();i++){
    //     cout <<i<<'\t';
    //     for (set<pair<int, int> >::const_iterator item=COLLECTION[i].begin();item!=COLLECTION[i].end();item++){
    //         cout <<'('<<item->first<<','<<item->second<<") ";
    //     }
    //     cout <<endl;
    // }

    // 打印slr表
    // for (int i=0;i<GOTO.size();i++){
    //     cout <<i<<'\t';
    //     for (SetStringIterator symbol=symbols.begin();symbol!=symbols.end();symbol++){
    //         cout <<'('<<*symbol<<','<<GOTO[i][*symbol]<<") ";
    //     }
    //     // cout << GOTO[i].size();
    //     cout <<endl;
    // }
}


void print_slr(vector<map<string, int> > GOTO, set<string> symbols) {
    cout << setiosflags(ios::left) << "构造SLR分析表如下：" << endl;
    cout << setiosflags(ios::left) << setw(5) << " ";
    cout << setiosflags(ios::left) << setw(30) << "ACTION";
    cout << setiosflags(ios::left) << setw(10) << "GOTO" << endl;
    cout << setiosflags(ios::left) << setw(5) << "状态" << endl;
    cout << setiosflags(ios::left) << setw(5) << " ";
    for (SetStringIterator symbol = symbols.begin(); symbol != symbols.end(); symbol++) {
        if (nonterminal_symbols.find(*symbol) == nonterminal_symbols.end())cout << setiosflags(ios::left) << setw(5) << *symbol << " ";
    }
    for (SetStringIterator symbol = symbols.begin(); symbol != symbols.end(); symbol++) {
        if (nonterminal_symbols.find(*symbol) != nonterminal_symbols.end())cout << setiosflags(ios::left) << setw(5) << *symbol << " ";
    }
    cout << endl;
    for (int i = 0; i < GOTO.size(); i++) {
        cout << setiosflags(ios::left) << setw(5) << i;
        for (SetStringIterator symbol = symbols.begin(); symbol != symbols.end(); symbol++) {
            if (nonterminal_symbols.find(*symbol) == nonterminal_symbols.end()) {
                int m = GOTO[i][*symbol];
                if (m < 0) {
                    if ((-(m + 1)) == 0) {
                        cout << setiosflags(ios::left) << setw(6) << "acc";
                    }
                    else {
                        cout << setiosflags(ios::left) << setw(1) << "r";
                        cout << setiosflags(ios::left) << setw(5) << -(m + 1);
                    }

                }
                else if (m > 0) {
                    cout << setiosflags(ios::left) << setw(1) << "S";
                    cout << setiosflags(ios::left) << setw(5) << m;
                }
                else cout << setiosflags(ios::left) << setw(6) << "    ";
            }
        }
        for (SetStringIterator symbol = symbols.begin(); symbol != symbols.end(); symbol++) {
            if (nonterminal_symbols.find(*symbol) != nonterminal_symbols.end()) {
                if (GOTO[i][*symbol] != 0)
                    cout << setiosflags(ios::left) << setw(6) << GOTO[i][*symbol];
                else cout << setiosflags(ios::left) << setw(6) << " ";
            }
        }
        // cout << GOTO[i].size();
        cout << endl;
    }
}

// 读取单词符号序列（tokens）
vector<string> parse_tokens(const char* filename) {
    ifstream file(filename);
    if (!file){
        cout << "can not open the file: " << filename << endl;
        exit(1);
    }
    vector<string> tokens;
    string line;
    string _FLOAT = "FLOAT",_IDN="IDN",_INT="INT";
    // 逐行读取 tokens流
    while (getline(file, line)) {
        // cout << line <<endl;
        stringstream ss(line);
        string token, type_content;
        getline(ss, token, ' ');  // Extract the token
        getline(ss, type_content, ' ');  // Extract the type and content
        if(type_content.find(_INT)!=string::npos)
        {
            tokens.push_back("INT");
        }
        else if(type_content.find(_FLOAT)!=string::npos)
        {
            tokens.push_back("FLOAT");
        }
        else if(type_content.find(_IDN)!=string::npos)
        {
            tokens.push_back("IDN");
        }
        else tokens.push_back(token);
    }
    // 打印tokens
    // for (int i=0;i<tokens.size();i++){
    //     cout <<tokens[i]<<endl;
    // }

    return tokens;  // 返回读取到的 token序列
}

// 解析token序列
void parse_input(const vector<string>& tokens, string output_file) {
    ofstream output(output_file);  // 语法分析输出文件
    if (!output){
        cout << "can not open the file: " << output_file << endl;
        exit(1);
    }

    stack<int> states;  // 状态栈
    states.push(0);  // 起始状态

    stack<string> stack_symbols;    // 符号栈
    stack_symbols.push("BOF");  // Beginning of file marker for the stack

    vector<string> input(tokens);   // 输入序列
    input.push_back("#");  // End of input marker

    int ip = 0;  // Input pointer
    int step = 1;  // Step counter

    while (true) {
        int current_state = states.top();   // 当前状态
        string next_token = input[ip];      // 输入token
        // 查询 lr分析表
        map<string,int>::iterator action = GOTO[current_state].find(next_token);

        // 语法错误
        if (action == GOTO[current_state].end()) {
            // 写入文件
            output << step << "\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
            // cout << "[" << step << "]\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
            break;
        }

        int next_state = action->second;    // 下一状态
        string top_symbol = stack_symbols.top();   // 栈顶符号

        if (next_state >= 0) {  // 移入 move
            // 写入文件
            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "move" << endl;
            // cout << "[" << step << "]\t" << top_symbol << "#" << next_token << "\t" << "move" << endl;
            states.push(next_state);    // 状态进栈
            stack_symbols.push(next_token); // token进栈
            ip++;  // 读取下一token
        }
        else if (next_state < -1) {  // 归约 reduction
            // 获取 归约 产生式
            int production_index = -next_state - 1;
            Production prod = grammar[production_index];
            // int rhs_size = prod.right.size();
            int rhs_size;
            if (prod.right[0]=="$") rhs_size=0;
            else rhs_size = prod.right.size();

            // 写入文件
            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "reduction " << endl;
            // cout << "[" << step << "]\t" << top_symbol << "#" << next_token << "\t" << "reduction " <<production_index+1<< endl;
            // for (VectorStringIterator sym=prod.right.begin();sym<prod.right.end();sym++) output << *sym << " ";
            // output << endl;

            // 开始归约
            for (int i = 0; i < rhs_size; ++i) {
                states.pop();   // 状态出栈
                stack_symbols.pop();    // 符号出栈
            }
            stack_symbols.push(prod.left);  // 归约后的非终结符进栈

            // 查 GOTO表 新状态进栈
            map<string,int>::iterator goto_action = GOTO[states.top()].find(prod.left);
            // 语法错误
            if (goto_action == GOTO[states.top()].end()){
                // 写入文件
                output << step << "\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
                // cout << "2[" << step << "]\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
                break;
            }
            states.push(goto_action->second);   // 状态进栈
        }
        else if (next_state == -1) {  // Accept
            // 写入文件
            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "accept" << endl;
            // cout << "[" << step << "]\t" << top_symbol << "#" << next_token << "\t" << "accept" << endl;
            break;
        }

        step++;
    }

    output.close();  // Close the file after writing
}

int main() {
    read_grammar();  //文法读入
    compute_first(); //计算FIRST集
    compute_follow(); //计算FOLLOW集
    construct_slr_table(); //构造SLR(1)分析表
    // print_slr(GOTO, symbols); //打印SLR(1)分析表
    vector<string> input_tokens = parse_tokens("./result-lexical/lexical_05_var_defn.txt");
    parse_input(input_tokens, "./result-syntax/syntax_05_var_defn.txt"); //根据token流进行移进规约分析并将结果保存在syntax_result.txt中
    return 0;
}
